import java.util.*;

public class TopK {

    /**
     * 求前k个最小的元素
     * @param array
     * @param k
     */
    public static int[] topK(int[] array, int k) {
//        1.创建一个大小为k的大根堆  不传值默认是1
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;//大根堆
                }
            }
        );

//        2.遍历数组中的元素 将k个元素放到队列中
        for (int i = 0; i < array.length; i++) {
            if (maxHeap.size() < k) {
                maxHeap.offer(array[i]);
            }else {
//                3.从k+1个元素开始每个元素和对顶元素比较 如果比对顶元素小 就交换
                int top = maxHeap.peek();
                if (top > array[i]) {
//                    3.1先弹出   每次弹出 和 添加都会调整
                    maxHeap.poll();
//                    3.2后存入
                    maxHeap.offer(array[i]);
                }
            }
        }

        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = maxHeap.poll();
        }
        return tmp;
    }



//    373. 查找和最小的 K 对数字
//      给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
//      定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
//      请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。

    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1)) - (o1.get(0)+o1.get(1));
            }
        });

        for (int i = 0; i < Math.min(nums1.length,k); i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {
                if (maxHeap.size() < k) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    maxHeap.offer(list);
                } else {
                    int top = maxHeap.peek().get(0) + maxHeap.peek().get(1);
                    if (top > nums1[i]+nums2[j]) {
                        maxHeap.poll();
                        List<Integer> list = new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        maxHeap.offer(list);
                    }
                }
            }
        }
        List<List<Integer>> ret = new ArrayList<>();
//        如果两个数组 组成的数对数量小于k   继续运行会空指针异常 所以!maxHeap.isEmpty()判断条件
        for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {
            ret.add(maxHeap.poll());
        }
        return ret;
    }













    public static void main1(String[] args) {
        int[] array = {18,21,8,10,34,12};
        int[] tmp = topK(array,3);
        System.out.println(Arrays.toString(tmp));//[12, 10, 8]
    }


    public static void main(String[] args) {
        int[] num1 = {1,1,2};
        int[] num2 = {1,2,3};
        List<List<Integer>> ret = kSmallestPairs(num1,num2,2);
        System.out.println(ret);//[[1, 1], [1, 1]]
    }

}
